package com.king.string;

import java.util.List;

import com.google.common.collect.Lists;

/**
 * @author taomk
 * @version 1.0
 * @since 15-1-31 下午9:38
 */
public class StringUtils {

	public static int indexOf(String src, String dest) {
		if (src == null || src.length() < 1) return -1;
		if (dest == null || dest.length() < 1) return -1;

		int[] indexes = indexesOf(src, dest);
		return indexes[0];
	}

	public static int lastIndexOf(String src, String dest) {
		if (src == null || src.length() < 1) return -1;
		if (dest == null || dest.length() < 1) return -1;

		int[] indexes = indexesOf(src, dest);
		return indexes[indexes.length-1];
	}

	/**
	 * 复杂度O(mn)
	 */
	public static int[] indexesOf(String src, String dest) {
		if (src == null || src.length() < 1) return new int[]{-1};
		if (dest == null || dest.length() < 1) return new int[]{-1};

		char[] srcArray = src.toCharArray();
		char[] destArray = dest.toCharArray();

		List<Integer> indexes = Lists.newArrayList();
		for (int i = 0 ; i < srcArray.length; i++) {
			int j = 0;
			for (; j < destArray.length; j++) {
				if (srcArray[i+j] != destArray[j]) {
					break;
				}
			}
			if (j == destArray.length) {
				// already found
				indexes.add(i);
			}
		}

		int[] ins = new int[indexes.size()];
		int i = 0;
		for (Integer I : indexes) {
			ins[i++] = I;
		}
		return ins;
	}

	public static int indexOfByBM(String src, String dest) {
		if (src == null || src.length() < 1) return -1;
		if (dest == null || dest.length() < 1) return -1;

		int[] indexes = indexesOfByBM(src, dest);
		return indexes[0];
	}

	/**
	 * TODO Boyer-Moore算法
	 * http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
	 */
	public static int[] indexesOfByBM(String src, String dest) {

		if (src == null || src.length() < 1) return new int[]{-1};
		if (dest == null || dest.length() < 1) return new int[]{-1};


		return null;
	}

	public int[] indexesOfByKMP(String src, String dest) {

		if (src == null || src.length() < 1) return new int[]{-1};
		if (dest == null || dest.length() < 1) return new int[]{-1};

		char[] srcArray = src.toCharArray();
		char[] destArray = dest.toCharArray();
		int[] partialMatchTable = countPartialMatchTable(destArray);
		List<Integer> index = Lists.newArrayList();

		int i = 0;
		while(i < srcArray.length) {
			int partMatch = 0 ;
			for (int j = 0 ;j < destArray.length; j++) {
				if (srcArray[i+j] == destArray[j]) {
					++partMatch;	// 部分匹配的标志
				} else {
					break;
				}
			}
			// 已经找到
			if (partMatch == destArray.length) {
				index.add(i);
			}
			if (partMatch > 0 ) {
				i += partMatch - partialMatchTable[partMatch-1];
			} else {
				i++;
			}
		}

		int[] ins = new int[index.size()];
		int j = 0;
		for (Integer I : index) {
			ins[j++] = I;
		}

		return ins;
	}

	public int indexOfByKMP(String src, String dest) {
		if (src == null || src.length() < 1) return -1;
		if (dest == null || dest.length() < 1) return -1;

		char[] srcArray = src.toCharArray();
		char[] destArray = dest.toCharArray();
		int[] partialMatchTable = countPartialMatchTable(destArray);
		int index = -1;

		int i = 0;
		while(i < srcArray.length) {
			int partMatch = 0 ;
			for (int j = 0 ;j < destArray.length; j++) {
				if (srcArray[i+j] == destArray[j]) {
					++partMatch;	// 部分匹配的标志
				} else {
					break;
				}
			}
			// 已经找到
			if (partMatch == destArray.length) {
				return i;
			}
			if (partMatch > 0 ) {
				i += partMatch - partialMatchTable[partMatch-1];
			} else {
				i++;
			}
		}

		return index;
	}

	/**
	 * 根据被searh字符串计算部分匹配表
	 * TODO 可以考虑缓存 部分匹配表
	 * @param chars
	 *
	 * ************************************************
	 * －"A"的前缀和后缀都为空集，共有元素的长度为0；
	 * －"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
	 * －"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
	 * －"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
	 * －"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
	 * －"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
	 * － "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
	 * ************************************************
	 *
	 * @return
	 */
	private static int[] countPartialMatchTable(char[] chars) {
		int[] partialMatchTable = new int[chars.length];
		// 第一个元素的部分匹配值必为0
		partialMatchTable[0] = 0;
		for (int i = 1 ; i < chars.length; i++) {
			String[] pre = new String[i];
			String[] suf = new String[i];

			for (int j = 0; j < i; j++) {
				char[] tempPre = new char[j+1];
				System.arraycopy(chars, 0, tempPre, 0, j+1);
				pre[j] = String.valueOf(tempPre);

				char[] tempSuf = new char[j+1];
				System.arraycopy(chars, i-j, tempSuf, 0, j+1);
				suf[j] = String.valueOf(tempSuf);
			}

			for (int j = 0; j < i; j++) {
				if (pre[j].equals(suf[j])) {
					partialMatchTable[i] = j+1;
					break;
				} else {
					partialMatchTable[i] = 0;
				}
			}
		}
		return partialMatchTable;
	}

	public static void main(String [] args) {
		String dest = "ABCDABD";
		int[] tb = countPartialMatchTable(dest.toCharArray());
		for (int i = 0; i < tb.length; i++) {
			System.out.println(tb[i]);
		}

		String src = "BBC ABCDAB ABCDABCDABDE";
		System.out.println("index is: " + indexOf(src, dest));

		int[] ins = indexesOf(src, dest);
		System.out.print("indexes are:");
		for (int i : ins) {
			System.out.print(" "+i+" ,");
		}

		System.out.println();
		ins = indexesOf("good morning what is yor name, or", "or");
		System.out.print("indexes are:");
		for (int i : ins) {
			System.out.print(" "+i+" ,");
		}
	}
}
